package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/22 10:26
 */
public class Title743III {

    /**
     * startId -> curId的距离
     */
    class State{
        int id;

        int distance;

        public State(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        //构建图<i,<j,v>>
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge : times) {
            graph.computeIfAbsent(edge[0], g -> new HashMap<>()).put(edge[1], edge[2]);
        }

        //各个顶点之间的距离
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        Queue<State> queue = new PriorityQueue<>((a, b)->(Integer.compare(a.distance, b.distance)));
        queue.offer(new State(k, 0));
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curId = state.id;
            int curDist = state.distance;
            if (curDist > dist[curId]) {
                continue;
            }
            //计算该点到其他点的距离是否 < start点到其他点的距离
            Map<Integer, Integer> orDefault = graph.getOrDefault(curId, new HashMap<>());
            Set<Integer> integers = orDefault.keySet();
            for (Integer nextId : integers) {
                int nextDist = curDist + orDefault.get(nextId);
                if (nextDist < dist[nextId]) {
                    dist[nextId] = nextDist;
                    queue.offer(new State(nextId, nextDist));
                }
            }
        }
        int max = 0;
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            max = Math.max(max, dist[i]);
        }
        return max;
    }

    public static void main(String[] args) {

    }
}
